{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Unhappy Friends"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: unhappyFriends"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计不开心的朋友"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一份 <code>n</code> 位朋友的亲近程度列表，其中 <code>n</code> 总是 <strong>偶数</strong> 。</p>\n",
    "\n",
    "<p>对每位朋友 <code>i</code>，<code>preferences[i]</code> 包含一份 <strong>按亲近程度从高</strong><strong>到低排列</strong> 的朋友列表。换句话说，排在列表前面的朋友与 <code>i</code> 的亲近程度比排在列表后面的朋友更高。每个列表中的朋友均以 <code>0</code> 到 <code>n-1</code> 之间的整数表示。</p>\n",
    "\n",
    "<p>所有的朋友被分成几对，配对情况以列表 <code>pairs</code> 给出，其中 <code>pairs[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> 表示 <code>x<sub>i</sub></code> 与 <code>y<sub>i</sub></code> 配对，且 <code>y<sub>i</sub></code> 与 <code>x<sub>i</sub></code> 配对。</p>\n",
    "\n",
    "<p>但是，这样的配对情况可能会使其中部分朋友感到不开心。在 <code>x</code> 与 <code>y</code> 配对且 <code>u</code> 与 <code>v</code> 配对的情况下，如果同时满足下述两个条件，<code>x</code> 就会不开心：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>x</code> 与 <code>u</code> 的亲近程度胜过 <code>x</code> 与 <code>y</code>，且</li>\n",
    "\t<li><code>u</code> 与 <code>x</code> 的亲近程度胜过 <code>u</code> 与 <code>v</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>返回 <strong>不开心的朋友的数目</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], pairs = [[0, 1], [2, 3]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "朋友 1 不开心，因为：\n",
    "- <strong>1 与 0 </strong>配对，但 <strong>1 与 3</strong> 的亲近程度比 <strong>1 与 0</strong> 高，且\n",
    "- <strong>3 与 1</strong> 的亲近程度比 <strong>3 与 2</strong> 高。\n",
    "朋友 3 不开心，因为：\n",
    "- 3 与 2 配对，但 <strong>3 与 1</strong> 的亲近程度比 <strong>3 与 2</strong> 高，且\n",
    "- <strong>1 与 3</strong> 的亲近程度比 <strong>1 与 0</strong> 高。\n",
    "朋友 0 和 2 都是开心的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, preferences = [[1], [0]], pairs = [[1, 0]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>朋友 0 和 1 都开心。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]], pairs = [[1, 3], [0, 2]]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 500</code></li>\n",
    "\t<li><code>n</code> 是偶数</li>\n",
    "\t<li><code>preferences.length&nbsp;== n</code></li>\n",
    "\t<li><code>preferences[i].length&nbsp;== n - 1</code></li>\n",
    "\t<li><code>0 &lt;= preferences[i][j] &lt;= n - 1</code></li>\n",
    "\t<li><code>preferences[i]</code> 不包含 <code>i</code></li>\n",
    "\t<li><code>preferences[i]</code> 中的所有值都是独一无二的</li>\n",
    "\t<li><code>pairs.length&nbsp;== n/2</code></li>\n",
    "\t<li><code>pairs[i].length&nbsp;== 2</code></li>\n",
    "\t<li><code>x<sub>i</sub> != y<sub>i</sub></code></li>\n",
    "\t<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub>&nbsp;&lt;= n - 1</code></li>\n",
    "\t<li>每位朋友都 <strong>恰好</strong> 被包含在一对中</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-unhappy-friends](https://leetcode.cn/problems/count-unhappy-friends/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-unhappy-friends](https://leetcode.cn/problems/count-unhappy-friends/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[1,2,3],[3,2,0],[3,1,0],[1,2,0]]\\n[[0,1],[2,3]]', '2\\n[[1],[0]]\\n[[1,0]]', '4\\n[[1,3,2],[2,3,0],[1,3,0],[0,2,1]]\\n[[1,3],[0,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        order = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1):\n",
    "                order[i][preferences[i][j]] = j\n",
    "        \n",
    "        match = [0] * n\n",
    "        for x, y in pairs:\n",
    "            match[x] = y\n",
    "            match[y] = x\n",
    "\n",
    "        unhappyCount = 0\n",
    "        for x in range(n):\n",
    "            y = match[x]\n",
    "            index = order[x][y]\n",
    "            for i in range(index):\n",
    "                u = preferences[x][i]\n",
    "                v = match[u]\n",
    "                if order[u][x] < order[u][v]:\n",
    "                    unhappyCount += 1\n",
    "                    break\n",
    "        \n",
    "        return unhappyCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        unhappy_counts = 0\n",
    "        couples = {}  # 配对情况表，用一个哈希表代替，O(1)\n",
    "        for i, j in pairs:  # 核心在于建立个字典，查询正牌couple\n",
    "            couples[i] = j\n",
    "            couples[j] = i\n",
    "        # n个人，逐一判断是否开心\n",
    "        for x in range(n):\n",
    "            # 切片找到配对亲密的朋友，\n",
    "            # 如果是preferences[0:0],这个for就不会启动，所以u必然有\n",
    "            for goddess in preferences[x][0:preferences[x].index(couples[x])]:\n",
    "                # 看女神笔记本里的备胎排名,如果自己排名比她的正牌高，自己就不开心\n",
    "                if preferences[goddess].index(x) < preferences[goddess].index(couples[goddess]):\n",
    "                    unhappy_counts += 1\n",
    "                    break\n",
    "        return unhappy_counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        if len(preferences) == 1:\n",
    "            return 0\n",
    "        happy_cnt = [0] * n\n",
    "        ans = 0\n",
    "        for pair in pairs:\n",
    "            happy_cnt[pair[0]] = preferences[pair[0]].index(pair[1])\n",
    "            happy_cnt[pair[1]] = preferences[pair[1]].index(pair[0])\n",
    "        for i, pre in enumerate(preferences):\n",
    "            for j, friend in enumerate(pre):\n",
    "                if j >= happy_cnt[i]:\n",
    "                    break\n",
    "                if preferences[friend].index(i) < happy_cnt[friend]:\n",
    "                    ans += 1\n",
    "                    break\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        pairsx = [-1 for i in range(n)]\n",
    "        for pair in pairs:\n",
    "            pairsx[pair[0]] = pair[1]\n",
    "            pairsx[pair[1]] = pair[0]\n",
    "        sadnessx = [[-1 for i in range(n)] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n-1):\n",
    "                sadnessx[i][preferences[i][j]] = j\n",
    "        cnt = 0\n",
    "        for pair in pairs:\n",
    "            for i in range(sadnessx[pair[0]][pair[1]]):\n",
    "                u = preferences[pair[0]][i]\n",
    "                if(sadnessx[u][pairsx[u]] > sadnessx[u][pair[0]]):\n",
    "                    cnt += 1\n",
    "                    break\n",
    "            for i in range(sadnessx[pair[1]][pair[0]]):\n",
    "                u = preferences[pair[1]][i]\n",
    "                if(sadnessx[u][pairsx[u]] > sadnessx[u][pair[1]]):\n",
    "                    cnt += 1\n",
    "                    break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        d_p = {}\n",
    "        res = 0\n",
    "        for p in pairs:\n",
    "            d_p[p[0]] = p[1]\n",
    "            d_p[p[1]] = p[0]\n",
    "\n",
    "        visited = ()\n",
    "        print(d_p)\n",
    "        \n",
    "        for i in range(len(preferences)):\n",
    "            if preferences[i][0] == d_p[i]:\n",
    "                continue\n",
    "            for pre in preferences[i]:\n",
    "                if pre == d_p[i]:\n",
    "                    break\n",
    "                if preferences[pre].index(i) < preferences[pre].index(d_p[pre]):\n",
    "                    res += 1\n",
    "                    break\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "        #    if i not in visited:\n",
    "        #         for p in preferences[i]:\n",
    "        #             if p == d[i]:\n",
    "        #                 break\n",
    "        #             for p2 in preferences[p]:\n",
    "        #                 if p2 == d[p]:\n",
    "        #                     break;\n",
    "        #                 if p2 == i:\n",
    "        #                     res += 1\n",
    "        #                     break\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:  \n",
    "        pair = {}\n",
    "        not_happy = {}\n",
    "\n",
    "        for i in range(len(pairs)):\n",
    "            pair[pairs[i][0]] = pairs[i][1]\n",
    "            pair[pairs[i][1]] = pairs[i][0]\n",
    "            not_happy[pairs[i][0]] = False\n",
    "            not_happy[pairs[i][1]] = False\n",
    "        p = []\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            p.append([0]*n)\n",
    "        for i in range(len(preferences)):\n",
    "            for j in range(len(preferences[i])):\n",
    "                p[i][preferences[i][j]] = j\n",
    "        for i in range(n):\n",
    "            y = pair[i]\n",
    "            index = p[i][y]\n",
    "            for j in range(0,index):\n",
    "                if p[preferences[i][j]][i] < p[preferences[i][j]][pair[preferences[i][j]]]:\n",
    "                    res+=1\n",
    "                    break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        d_p = {}\n",
    "        res = 0\n",
    "        for p in pairs:\n",
    "            d_p[p[0]] = p[1]\n",
    "            d_p[p[1]] = p[0]\n",
    "        \n",
    "        for i in range(len(preferences)):\n",
    "            for pre in preferences[i]:\n",
    "                if pre == d_p[i]:\n",
    "                    break\n",
    "                if preferences[pre].index(i) < preferences[pre].index(d_p[pre]):\n",
    "                    res += 1\n",
    "                    break\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        order = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n-1):\n",
    "                order[i][preferences[i][j]] = j\n",
    "        \n",
    "        match = [0] * n\n",
    "        for x , y in pairs:\n",
    "            match[x] = y\n",
    "            match[y] = x\n",
    "        \n",
    "        un_happy_cnt = 0 \n",
    "        for x in range(n):\n",
    "            y = match[x]\n",
    "            index = order[x][y]\n",
    "            for i in range(index):\n",
    "                u = preferences[x][i]\n",
    "                v = match[u]\n",
    "                if order[u][x] < order[u][v]:\n",
    "                    un_happy_cnt += 1\n",
    "                    break\n",
    "        return un_happy_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        mark = [[0] * n for _ in range(n)]\n",
    "        for i, pref in enumerate(preferences):\n",
    "            cur = n - 1\n",
    "            for people in pref:\n",
    "                mark[i][people] = cur\n",
    "                cur -= 1\n",
    "        ans = set()\n",
    "\n",
    "        for i in range(len(pairs)):\n",
    "            for j in range(i):\n",
    "                x, y = pairs[i]\n",
    "                u, v = pairs[j]\n",
    "                if mark[x][y] < mark[x][u] and mark[u][v] < mark[u][x]:\n",
    "                    ans.add(u)\n",
    "                    ans.add(x)\n",
    "                if mark[y][x] < mark[y][u] and mark[u][v] < mark[u][y]:\n",
    "                    ans.add(u)\n",
    "                    ans.add(y)\n",
    "                if mark[x][y] < mark[x][v] and mark[v][u] < mark[v][x]:\n",
    "                    ans.add(v)\n",
    "                    ans.add(x)\n",
    "                if mark[y][x] < mark[y][v] and mark[v][u] < mark[v][y]:\n",
    "                    ans.add(v)\n",
    "                    ans.add(y)\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        memo = [0] * n\n",
    "        for x, y in pairs:\n",
    "            if not memo[x]:\n",
    "                memo[x] = preferences[x][:preferences[x].index(y)]\n",
    "            if not memo[y]:\n",
    "                memo[y] = preferences[y][:preferences[y].index(x)]\n",
    "        \n",
    "        return sum(any(i in memo[j] for j in memo[i]) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        memo = {}  # person x: person x（相比pairs中的搭档y）更prefer去组合的人\n",
    "        for x, y in pairs:\n",
    "            memo[x] = preferences[x][:preferences[x].index(y)]\n",
    "            memo[y] = preferences[y][:preferences[y].index(x)]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in memo[i]:  # 对于i更prefer的每个人j\n",
    "                if i in memo[j]:  # 如果j也更prefer i\n",
    "                    res += 1\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        if len(preferences) == 1:\n",
    "            return 0\n",
    "        happy_cnt = [0] * n\n",
    "        ans = 0\n",
    "        for pair in pairs:\n",
    "            happy_cnt[pair[0]] = preferences[pair[0]].index(pair[1])\n",
    "            happy_cnt[pair[1]] = preferences[pair[1]].index(pair[0])\n",
    "        for i, pre in enumerate(preferences):\n",
    "            for j, friend in enumerate(pre):\n",
    "                if j < happy_cnt[i] and preferences[friend].index(i) < happy_cnt[friend]:\n",
    "                    ans += 1\n",
    "                    break\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        happy = [True] * n\n",
    "        prefer = [[False for _ in range(n)] for _ in range(n)]\n",
    "        spouse = [-1 for _ in range(n)]\n",
    "        for pair in pairs:\n",
    "            spouse[pair[0]] = pair[1]\n",
    "            spouse[pair[1]] = pair[0]\n",
    "        for i in range(n):\n",
    "            for j in preferences[i]:\n",
    "                if j == spouse[i]:\n",
    "                    break\n",
    "                prefer[i][j] = True\n",
    "                if prefer[j][i]:\n",
    "                    happy[i] = False\n",
    "                    happy[j] = False\n",
    "        return happy.count(False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        couple_of_ = {}\n",
    "        for you , other  in pairs:\n",
    "            couple_of_[you] = other\n",
    "            couple_of_[other] = you\n",
    "        sad_person = 0\n",
    "        for person in range(n):\n",
    "            couple = couple_of_[person]\n",
    "            for lover in preferences[person][:preferences[person].index(couple)]:\n",
    "                real_in_love = couple_of_[lover]\n",
    "                if preferences[lover].index(person) < preferences[lover].index(real_in_love):\n",
    "                    sad_person += 1\n",
    "                    break\n",
    "        return sad_person\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        order = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1):\n",
    "                order[i][preferences[i][j]] = j\n",
    "        \n",
    "        match = [0] * n\n",
    "        for x, y in pairs:\n",
    "            match[x] = y\n",
    "            match[y] = x\n",
    "\n",
    "        unhappyCount = 0\n",
    "        for x in range(n):\n",
    "            y = match[x]\n",
    "            index = order[x][y]\n",
    "            for i in range(index):\n",
    "                u = preferences[x][i]\n",
    "                v = match[u]\n",
    "                if order[u][x] < order[u][v]:\n",
    "                    unhappyCount += 1\n",
    "                    break\n",
    "        \n",
    "        return unhappyCount\n",
    "\n",
    "# class Solution:\n",
    "#     def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "#         d_p = {}\n",
    "#         res = 0\n",
    "#         for p in pairs:\n",
    "#             d_p[p[0]] = p[1]\n",
    "#             d_p[p[1]] = p[0]\n",
    "        \n",
    "#         for i in range(len(preferences)):\n",
    "#             for pre in preferences[i]:\n",
    "#                 if pre == d_p[i]:\n",
    "#                     break\n",
    "#                 if preferences[pre].index(i) < preferences[pre].index(d_p[pre]):\n",
    "#                     res += 1\n",
    "#                     break\n",
    "#         return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        memo = [0] * n\n",
    "        for x, y in pairs:\n",
    "            memo[x] = preferences[x][:preferences[x].index(y)]\n",
    "            memo[y] = preferences[y][:preferences[y].index(x)]\n",
    "        \n",
    "        return sum(any(i in memo[j] for j in memo[i]) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        mark = [[0] * n for _ in range(n)]\n",
    "        for i, pref in enumerate(preferences):\n",
    "            for j, lover in enumerate(pref):\n",
    "                mark[i][lover] = j\n",
    "\n",
    "        couple = dict()\n",
    "        for a,b in pairs:\n",
    "            couple[a] = b\n",
    "            couple[b] = a\n",
    "\n",
    "        ans = 0\n",
    "        for x in range(n):\n",
    "            y = couple[x]\n",
    "            for u in range(n):\n",
    "                if u == x or u == y:\n",
    "                    continue\n",
    "                v = couple[u]\n",
    "                if mark[x][y] > mark[x][u] and mark[u][v] > mark[u][x]:\n",
    "                    ans += 1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        res = set()\n",
    "        def checkout_happy_friend(x, y):\n",
    "            u_list = []\n",
    "            for u in preferences[x]:\n",
    "                if u == y:\n",
    "                    break\n",
    "                else:\n",
    "                    u_list.append(u)\n",
    "            for u in u_list:\n",
    "                flag = False\n",
    "                for v in preferences[u]:\n",
    "                    if v == y:\n",
    "                        continue\n",
    "                    if v == x:\n",
    "                        flag = True\n",
    "                        continue\n",
    "                    if flag:\n",
    "                        if [u, v] in pairs or [v, u] in pairs:\n",
    "                            res.add(x)\n",
    "                            return\n",
    "        for x, y in pairs:\n",
    "            checkout_happy_friend(x, y)\n",
    "            checkout_happy_friend(y, x)\n",
    "        print(res)\n",
    "        return len(res)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        matrix = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1):\n",
    "                matrix[i][preferences[i][j]] = j\n",
    "        matches = [0 for _ in range(n)]\n",
    "        for pair in pairs:\n",
    "            matches[pair[0]] = pair[1]\n",
    "            matches[pair[1]] = pair[0]\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j and matrix[i][j] < matrix[i][matches[i]] and matrix[j][i] < matrix[j][matches[j]]:\n",
    "                    count += 1\n",
    "                    break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        # 记录每一个人的亲近程度顺位，0 1 2 3越来越低\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n-1):\n",
    "                f[i][preferences[i][j]] = j\n",
    "        \n",
    "        # 记录每一个人的pair\n",
    "        match = [0] * n\n",
    "        for x, y in pairs:\n",
    "            match[x] = y\n",
    "            match[y] = x\n",
    "        \n",
    "        unhappyCount = 0\n",
    "        for x in range(n):\n",
    "            # 获取pair\n",
    "            y = match[x]\n",
    "            index = f[x][y]\n",
    "            for i in range(index):\n",
    "                u = preferences[x][i]\n",
    "                v = match[u]\n",
    "                if f[u][x] < f[u][v]:\n",
    "                    unhappyCount += 1\n",
    "                    break\n",
    "        return unhappyCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        mat = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for i, vec in enumerate(preferences):\n",
    "            mat[i][i] = n \n",
    "            mat[i][vec[0]] = n-1\n",
    "            for j in range(1, len(vec)):\n",
    "                mat[i][vec[j]] = mat[i][vec[j-1]] - 1\n",
    "        #print(mat) \n",
    "        ans = set() \n",
    "        for i, (a1, b1) in enumerate(pairs):\n",
    "            for j, (a2, b2) in enumerate(pairs):\n",
    "                if i!=j:\n",
    "                    for [x, y] in [[a1, b1], [b1, a1]]:\n",
    "                        for [u, v] in [[a2, b2], [b2, a2]]:\n",
    "                            if mat[x][u] > mat[x][y] and mat[u][x] > mat[u][v]:\n",
    "                                ans.add(x)\n",
    "        return len(ans) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        Like = [[-1] * n for _ in range(n)]\n",
    "        for x, p in enumerate(preferences):\n",
    "            for i, y in enumerate(p):\n",
    "                Like[x][y] = i\n",
    "\n",
    "        def check(x: int, y: int, u: int, v: int) -> bool:\n",
    "            return Like[x][u] < Like[x][y] and Like[u][x] < Like[u][v]\n",
    "\n",
    "        ans = 0\n",
    "        for x, y in pairs:\n",
    "            f1, f2 = 0, 0\n",
    "            for x1, y1 in pairs:\n",
    "                if x1 == x and y1 == y: continue\n",
    "                f1 |= check(x, y, x1, y1)\n",
    "                f1 |= check(x, y, y1, x1)\n",
    "                f2 |= check(y, x, x1, y1)\n",
    "                f2 |= check(y, x, y1, x1)\n",
    "            ans += f1 + f2\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        pref = [[None] * n for _ in range(n)]\n",
    "        for i, values in enumerate(preferences):\n",
    "            score = n - 1\n",
    "            for j in values:\n",
    "                pref[i][j] =  score\n",
    "                score -= 1\n",
    "        match = [None] * n\n",
    "        for i, j in pairs:\n",
    "            match[i] = j\n",
    "            match[j] = i\n",
    "        \n",
    "        for i in range(n):\n",
    "            y = match[i]\n",
    "            if pref[i][y] == n - 1:\n",
    "                continue\n",
    "            for u in preferences[i]:\n",
    "                if u == y:\n",
    "                    break\n",
    "                v = match[u]\n",
    "                if pref[u][i] > pref[u][v]:\n",
    "                    count += 1\n",
    "                    break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        order = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1):\n",
    "                order[i][preferences[i][j]] = j\n",
    "        match = [0] * n\n",
    "        for x, y in pairs:\n",
    "            match[x] = y\n",
    "            match[y] = x\n",
    "        for i in range(n):\n",
    "            y = match[i]\n",
    "            index = order[i][y]\n",
    "            for j in range(index):\n",
    "                u = preferences[i][j]\n",
    "                v = match[u]\n",
    "                if order[u][i] < order[u][v]:\n",
    "                    res += 1\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        mark = [[0] * n for _ in range(n)]\n",
    "        for i, pref in enumerate(preferences):\n",
    "            cur = n - 1\n",
    "            for people in pref:\n",
    "                mark[i][people] = cur\n",
    "                cur -= 1\n",
    "        ans = set()\n",
    "\n",
    "        for i in range(len(pairs)):\n",
    "            for j in range(i):\n",
    "                x, y = pairs[i]\n",
    "                u, v = pairs[j]\n",
    "                if mark[x][y] < mark[x][u] and mark[u][v] < mark[u][x]:\n",
    "                    ans.add(u)\n",
    "                    ans.add(x)\n",
    "                if mark[y][x] < mark[y][u] and mark[u][v] < mark[u][y]:\n",
    "                    ans.add(u)\n",
    "                    ans.add(y)\n",
    "                if mark[x][y] < mark[x][v] and mark[v][u] < mark[v][x]:\n",
    "                    ans.add(v)\n",
    "                    ans.add(x)\n",
    "                if mark[y][x] < mark[y][v] and mark[v][u] < mark[v][y]:\n",
    "                    ans.add(v)\n",
    "                    ans.add(y)\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        edges=[[0]*n for _ in range(n)]\n",
    "        for i,prefer in enumerate(preferences):\n",
    "            cnt=len(prefer)\n",
    "            for j in prefer:\n",
    "                edges[i][j]=cnt\n",
    "                cnt-=1\n",
    "        match=[0]*n\n",
    "        for x,y in pairs:\n",
    "            match[x]=y\n",
    "            match[y]=x\n",
    "        unhappy=0\n",
    "        for x in range(n):\n",
    "            y=match[x]\n",
    "            for u in preferences[x]:\n",
    "                if edges[x][u]>edges[x][y]:\n",
    "                    v=match[u]\n",
    "                    if edges[u][x]>edges[u][v]:\n",
    "                        unhappy+=1\n",
    "                        break\n",
    "        return unhappy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        k=len(pairs)\n",
    "        vis=[0]*(n)\n",
    "        for i in range(k-1):\n",
    "            for j in range(i+1,k):\n",
    "                x,y=pairs[i]\n",
    "                x1,y1=pairs[j]\n",
    "                if vis[x]==0:\n",
    "                    h=x\n",
    "                    p=y\n",
    "                    f1=x1\n",
    "                    f2=y1     \n",
    "                    hp=preferences[h].index(p)\n",
    "                    hf1=preferences[h].index(f1)\n",
    "                    hf2=preferences[h].index(f2)\n",
    "                    f1h=preferences[f1].index(h)\n",
    "                    f2h=preferences[f2].index(h)\n",
    "                    f1f2=preferences[f1].index(f2)\n",
    "                    f2f1=preferences[f2].index(f1)\n",
    "                    if hf1<hp and  f1h<f1f2:\n",
    "                        vis[h]=1\n",
    "                    elif hf2<hp and f2h<f2f1:\n",
    "                        vis[h]=1\n",
    "                if vis[y]==0:\n",
    "                    h=y\n",
    "                    p=x\n",
    "                    f1=x1\n",
    "                    f2=y1     \n",
    "                    hp=preferences[h].index(p)\n",
    "                    hf1=preferences[h].index(f1)\n",
    "                    hf2=preferences[h].index(f2)\n",
    "                    f1h=preferences[f1].index(h)\n",
    "                    f2h=preferences[f2].index(h)\n",
    "                    f1f2=preferences[f1].index(f2)\n",
    "                    f2f1=preferences[f2].index(f1)\n",
    "                    if hf1<hp and  f1h<f1f2:\n",
    "                        vis[h]=1\n",
    "                    elif hf2<hp and f2h<f2f1:\n",
    "                        vis[h]=1\n",
    "                if vis[x1]==0:\n",
    "                    h=x1\n",
    "                    p=y1\n",
    "                    f1=x\n",
    "                    f2=y   \n",
    "                    hp=preferences[h].index(p)\n",
    "                    hf1=preferences[h].index(f1)\n",
    "                    hf2=preferences[h].index(f2)\n",
    "                    f1h=preferences[f1].index(h)\n",
    "                    f2h=preferences[f2].index(h)\n",
    "                    f1f2=preferences[f1].index(f2)\n",
    "                    f2f1=preferences[f2].index(f1)\n",
    "                    if hf1<hp and  f1h<f1f2:\n",
    "                        vis[h]=1\n",
    "                    elif hf2<hp and f2h<f2f1:\n",
    "                        vis[h]=1\n",
    "                if vis[y1]==0:\n",
    "                    h=y1\n",
    "                    p=x1\n",
    "                    f1=x\n",
    "                    f2=y   \n",
    "                    hp=preferences[h].index(p)\n",
    "                    hf1=preferences[h].index(f1)\n",
    "                    hf2=preferences[h].index(f2)\n",
    "                    f1h=preferences[f1].index(h)\n",
    "                    f2h=preferences[f2].index(h)\n",
    "                    f1f2=preferences[f1].index(f2)\n",
    "                    f2f1=preferences[f2].index(f1)\n",
    "                    if hf1<hp and  f1h<f1f2:\n",
    "                        vis[h]=1\n",
    "                    elif hf2<hp and f2h<f2f1:\n",
    "                        vis[h]=1\n",
    "        cnt=0\n",
    "        for x in vis:\n",
    "            if x==1:\n",
    "                cnt+=1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        memo = [0] * n\n",
    "        for x, y in pairs:\n",
    "            if not memo[x]:\n",
    "                memo[x] = set(preferences[x][:preferences[x].index(y)])\n",
    "            if not memo[y]:\n",
    "                memo[y] = set(preferences[y][:preferences[y].index(x)])\n",
    "        \n",
    "        return sum(any(i in memo[j] for j in memo[i]) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n, preferences, pairs):\n",
    "        if len(preferences) == 1:\n",
    "            return 0\n",
    "        likes = [{} for _ in range(n)]\n",
    "        for i, p in enumerate(preferences):\n",
    "            for score, j in enumerate(p):\n",
    "                likes[i][j] = score\n",
    "\n",
    "        match = {}\n",
    "        for x, y in pairs:\n",
    "            match[x] = likes[x][y]\n",
    "            match[y] = likes[y][x]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for score, j in enumerate(preferences[i]):\n",
    "                if score >= match[i]:\n",
    "                    break\n",
    "                if likes[j][i] < match[j]:\n",
    "                    ans += 1\n",
    "                    break\n",
    "\n",
    "        return ans\n",
    "\n",
    "                \n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(\n",
    "        self, n: int, preferences: list[list[int]], pairs: list[list[int]]\n",
    "    ) -> int:\n",
    "        order: dict[int : dict[int, int]] = {}\n",
    "        for i, l in enumerate(preferences):\n",
    "            order[i] = {}\n",
    "            for j, v in enumerate(l):\n",
    "                order[i][v] = j\n",
    "\n",
    "        match = [0] * n \n",
    "        for i, v in enumerate(pairs):\n",
    "            match[v[0]] = v[1]\n",
    "            match[v[1]] = v[0]\n",
    "\n",
    "        res = 0\n",
    "        for x in range(0, n):\n",
    "            index = order[x][match[x]]\n",
    "            for u, i in order[x].items():\n",
    "                if i < index:\n",
    "                    v = match[u]\n",
    "                    if order[u][x] < order[u][v]:\n",
    "                        res += 1\n",
    "                        break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n, preferences, pairs):\n",
    "        likes = [{} for _ in range(n)]\n",
    "        for i, p in enumerate(preferences):\n",
    "            for score, j in enumerate(p):\n",
    "                likes[i][j] = score\n",
    "\n",
    "        match = {}\n",
    "        for x, y in pairs:\n",
    "            match[x] = likes[x][y]\n",
    "            match[y] = likes[y][x]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for score, j in enumerate(preferences[i]):\n",
    "                if score >= match[i]:\n",
    "                    break\n",
    "                if likes[j][i] < match[j]:\n",
    "                    ans += 1\n",
    "                    break\n",
    "\n",
    "        return ans\n",
    "\n",
    "                \n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n, preferences, pairs):\n",
    "        likes = [{} for _ in range(n)]\n",
    "        for i, p in enumerate(preferences):\n",
    "            for score, j in enumerate(p):\n",
    "                likes[i][j] = score\n",
    "\n",
    "        match = {}\n",
    "        for x, y in pairs:\n",
    "            match[x] = likes[x][y]\n",
    "            match[y] = likes[y][x]\n",
    "\n",
    "        # ans = 0\n",
    "        find = [False] * n\n",
    "        for i in range(n):\n",
    "            if find[i]:\n",
    "                continue\n",
    "            for score, j in enumerate(preferences[i]):\n",
    "                if score >= match[i]:\n",
    "                    break\n",
    "                if likes[j][i] < match[j]:\n",
    "                    find[i] = find[j] = True\n",
    "                    # ans += 1\n",
    "                    # print(i)\n",
    "                    break\n",
    "\n",
    "        return sum(find)\n",
    "\n",
    "                \n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:\n",
    "        # 创建亲近程度的评分字典\n",
    "        order = {}\n",
    "        for i in range(n):\n",
    "            order[i] = {}\n",
    "            for j, friend in enumerate(preferences[i]):\n",
    "                order[i][friend] = j\n",
    "        \n",
    "        # 创建配对字典\n",
    "        paired = {}\n",
    "        for x, y in pairs:\n",
    "            paired[x] = y\n",
    "            paired[y] = x\n",
    "        \n",
    "        # 检查不开心的朋友\n",
    "        unhappy_count = 0\n",
    "        for x in range(n):\n",
    "            y = paired[x]\n",
    "            x_pref_idx = order[x][y]\n",
    "            is_unhappy = False\n",
    "            for j in range(x_pref_idx):\n",
    "                u = preferences[x][j]\n",
    "                v = paired[u]\n",
    "                if order[u][x] < order[u][v]:\n",
    "                    is_unhappy = True\n",
    "                    break\n",
    "            if is_unhappy:\n",
    "                unhappy_count += 1\n",
    "        \n",
    "        return unhappy_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unhappyFriends(self, n, preferences, pairs):\n",
    "        likes = [{} for _ in range(n)]\n",
    "        for i, p in enumerate(preferences):\n",
    "            for score, j in enumerate(p):\n",
    "                likes[i][j] = score\n",
    "\n",
    "        match = {}\n",
    "        for x, y in pairs:\n",
    "            match[x] = likes[x][y]\n",
    "            match[y] = likes[y][x]\n",
    "\n",
    "        # ans = 0\n",
    "        find = [False] * n\n",
    "        for i in range(n):\n",
    "            if find[i]:\n",
    "                continue\n",
    "            for score, j in enumerate(preferences[i]):\n",
    "                if score >= match[i]:\n",
    "                    break\n",
    "                if likes[j][i] < match[j]:\n",
    "                    find[i] = find[j] = True\n",
    "                    # ans += 1\n",
    "                    # print(i)\n",
    "                    break\n",
    "\n",
    "        return sum(find)\n",
    "\n",
    "                \n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
